#include <iostream>
#include <vector>
#include <string>
#include <set>
using namespace std;
/**
 * @brief
 * 1 <= dictionary.length <= 1000
    1 <= dictionary[i].length <= 100
    dictionary[i] consists of only lower-case letters.
    1 <= sentence.length <= 10^6
    sentence consists of only lower-case letters and spaces.
    The number of words in sentence is in the range [1, 1000]
    The length of each word in sentence is in the range [1, 1000]
    Every two consecutive words in sentence will be separated by exactly one space.
    sentence does not have leading or trailing spaces.
 *
 */
struct Node
{
    char val;
    bool isend;
    struct Node *next[26];
};
class Trie
{
public:
    Node *root;
    Trie()
    {
        root = new Node(); //建立一个为空的根节点
    }

    void insert(string word)
    {
        Node *curr = root;
        for (int i = 0; i < word.size(); i++)
        {
            char c = word[i];
            //插入节点，先看看当前的node是否已经有指向该字母的next指针
            //如果没有，就新建一个指针
            if (curr->next[c - 'a'] == NULL)
            {
                curr->next[c - 'a'] = new Node();
            }
            //无论是新建还是原本存在，curr移动到该位置
            curr = curr->next[c - 'a'];
            curr->val = c; //这一步若是新建则为其赋值，不是新建赋值也无伤大雅
            if (i == word.size() - 1)
            {
                curr->isend = true;
            }
        }
    }

    string hasstartsWith(string &word)
    {
        Node *curr = root;
        for (int i = 0; i < word.size(); i++)
        {
            char c = word[i];
            curr = curr->next[c - 'a'];
            if (curr != nullptr && curr->isend)
            {
                return word.substr(0, i + 1);
            }
            if (curr == NULL)
            {
                return word;
            }
        }
        return word;
    }
};
class Solution
{
public:
    string replaceWords(vector<string> &dictionary, string sentence)
    {
        string ans;
        string::size_type pos;
        sentence += " ";
        int size = sentence.length(), dictLen = dictionary.size();
        for (int i = 0; i < size; i++)
        {
            pos = sentence.find(" ", i);
            if (pos < size)
            {
                string word = sentence.substr(i, pos - i);
                string root = word;
                for (int j = 0; j < dictLen; j++)
                {
                    if (word.find(dictionary[j]) == 0)
                    {
                        root = root.length() > dictionary[j].length() ? dictionary[j] : root;
                    }
                }
                ans += root + " ";
                // i=pos+pattern.size()-1
                i = pos;
            }
        }
        return ans.erase(ans.find_last_not_of(" ") + 1);
    }

    string replaceWords_2(vector<string> &dictionary, string sentence)
    {
        /**
         * @brief
         * save set ,order by length default
         *
         */

        set<string> dictSet;
        int size = dictionary.size();
        for (string dict : dictionary)
        {
            dictSet.insert(dict);
        }

        string res = "";
        size = sentence.size();
        for (int i = 0; i < size; ++i)
        {
            string temp = "";
            while (sentence[i] != ' ' && i < size)
            {
                temp += sentence[i];
                i++;
            }
            //空格刚好被跳过的
            // cout << temp << endl;
            int wordSize = temp.size();
            string root = temp, tempStr = "";
            // string find
            // for(string dict:dictSet){
            //     if (temp.find(dict)==0)
            //     {
            //         root=dict;
            //         break;
            //     }

            // }
            for (int i = 0; i < wordSize; i++)
            {
                tempStr += temp[i];
                if (dictSet.count(tempStr))
                {
                    root = tempStr;
                    tempStr = "";
                    break;
                }
            }

            res += root + ' ';
        }
        res.pop_back();
        return res;
    }

    string replaceWords_3(vector<string> &dictionary, string sentence)
    {
        Trie tree;
        for (auto &p : dictionary)
        {
            tree.insert(p);
        }
        string res,temp;
         sentence += ' ';
        int senLen=sentence.size();
       
        for (int i = 0; i < senLen; i++)
        {
            char ch = sentence[i];
            if (ch == ' ')
            {
                //判断是否存在根
                string in = tree.hasstartsWith(temp);
                res += in;
                if (i != senLen - 1)
                {
                    res += ' ';
                }
                temp.clear();
                continue;
            }
            temp += ch;
        }
        return res;
    }
};
int main()
{
    Solution s;
    vector<string> dictionary = {"a", "aa", "aaa", "aaaa"};
    string sentence = "a aa a aaaa aaa aaa aaa aaaaaa bbb baba ababa";
    cout << s.replaceWords_3(dictionary, sentence) << endl;
    return 0;
}
